# -*- coding: utf-8 -*-

"""剑指 Offer II 095. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。"""


class Solution:
    """此题一开始做毫无头绪，并不知道怎么来表示子序列。考虑到出现在动态规划范围里，既然无头绪，就先看看用回溯法怎么解决。
    思来想去，由草稿画图想到方向，就是选定一个字符串为参考序列(text1)，从其中拿出一个字符，遍历另一个字符串:=目标序列(text2)，形成一个 len(text1)*len(text2) 的矩阵。
    矩阵中 common[i][j] = 0: 字符不同 / 1: 字符相同，再计算从 [0][0] 到 [last][last] 所经过的最多相同点。
    移动方向有讲究，出发点为0，可以往右(i+1, j)，往下(i, j+1)，往右下(i+1, j+1)三个方向移动，
                出发点为1，但是没有消耗该对字符，也可以往右(i+1, j)，往下(i, j+1)，往右下(i+1, j+1)三个方向移动，
                出发点为1，并且消耗了该对字符，只能往右下方(i+1, j+1)一个方向移动
    
    最终选择消耗字符对最多的路径，既然选择最多的消耗，那就天然规避一些明显较小的情况，从目的到来源反查：
    对目的点 (i,j) 来说，最大的消耗对取决于左上角是否为1
    if from (i-1, j-1):    //可以消耗左上角的配对
        f(i,j) = f(i-1, j-1)+common[i-1][j-1]
    elif from (i-1, j) or from (i, j-1):    //不可消耗左边或者上边的配对
        f(i,j) = max(f(i-1, j), f(i, j-1))
    
    为了简化程序的实现，可以设置哨兵行列，即添加头行头列
    
      a c e
    a 1 0 0
    b 0 0 0
    c 0 1 0
    d 0 0 0
    e 0 0 1
    """
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        row_size, col_size = len(text1)+2, len(text2)+2
        martrix = [[0 for _ in range(col_size)] for _ in range(row_size)]
        for i, chi in zip(range(1, row_size-1), text1):
            for j, chj in zip(range(1, col_size-1), text2):
                martrix[i][j] = int(chi == chj)
        
        # for row in martrix:
        #     for col in row:
        #         print(col, end=',')
        #     print('')
        
        dp = [[0 for _ in range(col_size)] for _ in range(row_size)]
        for i in range(1, row_size):
            for j in range(1, col_size):
                # if martrix[i-1][j-1]:
                #     dp[i][j] = dp[i-1][j-1]+martrix[i-1][j-1]
                # else:
                #     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                dp[i][j] = max(dp[i-1][j-1]+martrix[i-1][j-1], dp[i-1][j], dp[i][j-1])
        # print('...........')
        # for row in dp:
        #     for col in row:
        #         print(col, end=',')
        #     print('')
        
        return dp[row_size-1][col_size-1]


if __name__ == '__main__':
    so = Solution()
    print(so.longestCommonSubsequence(text1 = "abcde", text2 = "ace"))
    print(so.longestCommonSubsequence(text1 = "abc", text2 = "abc"))
    print(so.longestCommonSubsequence(text1 = "abc", text2 = "def"))
    print(so.longestCommonSubsequence(text1 = "hofubmnylkra", text2 = "pqhgxgdofcvmr"))
